package q1182_shortestDistanceColor;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        int n = colors.length;
        // 分别记录每种颜色出现的位置
        List<Integer>[] lists = new List[4];
        // 初始化
        for (int i = 1; i < 4; i++)
            lists[i] = new ArrayList<>();

        List<Integer> res = new ArrayList<>();
        // 在每个color对应的index加上
        for(int i = 0; i < n; i++){
            lists[colors[i]].add(i);
        }


        for(int[] q : queries){
            // index 和 target
            int index = q[0], target = q[1];

            // 没有这个color的记录
            if(lists[target] == null || lists[target].size() == 0) {
                res.add(-1);
                continue;
            }
            // 红蓝二分搜索
            int left = -1, right = lists[target].size();
            // 注意，我们这里所需要的呢，只是普通的二分搜索，所以我们只用简单的设置就行
            // 一直让它收缩，最后退出left就是
            while(left + 1 != right) {
                int mid = (left + right) >> 1;
                if(lists[target].get(mid) <= index){
                    left = mid;
                }else{
                    right = mid;
                }
            }
            // left is what we want

            // 我们所需要的是相对距离，不是直接的返回值
            // 所有都是红色
            if(left == -1){
                res.add(lists[target].get(right) - index);
            }else if(right == lists[target].size()){//所有的都是蓝色
                res.add(index - lists[target].get(left));
            }else{
                // 查看左右距离
                res.add(Math.min(index - lists[target].get(left), lists[target].get(right) - index));
            }
        }
        return res;
    }
}
